The present invention relates to a multiprocessor system configured as a network containing a plurality of digital processors connected for mutual communication.
FIG. 1 is a block diagram for illustrating the basic principles of a prior art multiprocessor system, showing a portion of a generalized system. An arbitrarily selected digital processor (referred to in the following as a processing element) 29 is connected by respective bidirectional data lines such as lines 33 to 38 to a plurality of other processing elements, six of which are shown designated by numerals 26 to 32 respectively. Each of the processing elements is identified by a specific address which consist of a set of n digits (where n is an integer which is &gt;1) designated as P.sub.1, P.sub.2, . . . P.sub.n. FIG. 2 shows a specific example of such a prior art multiprocessor system, in which the processing elements are respectively designated by numerals 39 to 54, with respective addresses of (0,0,0,0) to (1,1,1,1). The number of processing elements in such a system, designated in the following as N, is given as N=R.sup..eta., where the base R is an integer which is greater than or equal to 2. With the multiprocessor system of FIG. 2, n is equal to 4 and R is equal to 2, i.e. this is a binary multiprocessor system having 2.sup.4 (=16) processing elements. Since each address has n digits, each of these digits is also determined to the base R, i.e. in the example of FIG. 2 each of these digits is a binary digit, or bit. Each processing element in such a system is connected to a total of n other processing elements, by n bidirectional data lines.
With the multiprocessor system of FIG. 2, the transfer of data between an arbitrary processing element having a address (P.sub.1, P.sub.2, . . . P.sub.i, . . . P.sub.n), and another processing element having address (Q.sub.1, Q.sub.2, . . . Q.sub.i, . . . Q.sub.n) where 1.ltoreq.i.ltoreq.n and each of P and Q is either 0 or 1, is performed by transferring the data through successively selected processing elements, with the addresses of these successively selected processing elements being determined by altering one bit of the address of the last selected processing element to thereby obtain the address of the processing element to be next selected, with these bit changes being made in a fixed direction such as to bring the address bits eventually into correspondence with those of the target processing element, i.e. (Q.sub.1, Q.sub.2, . . . Q.sub.i, . . . Q.sub.n).
For example, referring to FIG. 2, to transfer a data message from the processing element 47, whose address is (1,0,0,0) to the processing element 42 whose address is (0,0,1,1) the following procedure is executed. Firstly, designating the bits of each processing element as (P.sub.1, P.sub.2, P.sub.3, P.sub.4), it is found that the leading bit P.sub.1 of the destination address is 0. Data can be transferred from the processing element 47 to any of the processing elements 48, 49, 51 and 39. However of these, only processing element 39 has a address in which the leading bit is 0. The data are therefore first transferred to the processing element 39, whose address is (0,0,0,0). This is done by making a one-bit change in the address of the processing element 47. Next, since the second bit P.sub.2 of the destination address is 0, which is the same as that of the processing element 39, the third bit P.sub.3 of the destination address is examined. This is 1, and so the next processing element to be selected is processing element 41, in whose address (0,0,1,0) the third bit is 1. Next, since the fourth bit P.sub.4 of the destination address is 1, this address is selected by changing the fourth bit of the address of processing element 41 to 1. Data are then transferred to the destination processing element 42, with address (0,0,1,1). In this way, successive data transfer operations are executed by successive one-bit address changes, each of which brings the current address closer to the destination address. In this example, a total of three successive data transfer operations are required, to transmit a message from the source processing element to the destination processing element.
In the worst case for such data transfer, if all of the digits of the source and destination addresses are mutually different, a total of n transfer operation will be required. In addition with such a prior art multiprocessor system, a total of n data lines are connected to each processing element. Taking the general case of a base-2 system, in which the system has N=2.sup..eta. processing elements, the maximum number of data transfer operations required between a source processing element and a destination processing element will be log N/log 2 (=n), and the total number of data lines is equal to {(log N/log 2).times.N} (=n.times.N).
In the more general case of a base-R multiprocessor system in which the total number of processing elements N=R.sup.n, the maximum number of data transfer operations will be log N/log R (=n), and the total number of data lines will be: EQU {(log N/log R).times.N.times.(R-1)} (=n.times.N.times.(R-1)).
Thus with such a prior art multiprocessor system in which communication must be established between a total of N (=R.sup.n) processing elements, the number of bidirectional data lines which must be provided is proportional to N.times.log N.times.(R-1), if the maximum number of data transfer operations required to communicate between two arbitrary processing elements is to be limited to a value no greater than n. In the prior art, it is not possible to reduce this required number of data lines.
Such a prior art multiprocessor system has the disadvantage that it is necessary to provide bidirectional data lines between respective processing elements. Thus, the cost of the system hardware is high, e.g. due to the need to provide a plurality of bidirectional data input/output ports on each of the processing elements.